package merge;

import java.util.PriorityQueue;

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 思路 双指针
//        int []ans = new int[nums1.length];
//        int index = 0;
//        int p1 = 0;
//        int p2 = 0;
//        while(p1<m&&p2<n){
//            if(nums1[p1]<nums2[p2]){
//                ans[index++] = nums1[p1];
//                p1++;
//            }else {
//                ans[index++] = nums2[p2];
//                p2++;
//            }
//        }
//        while (p1<m){
//           ans[index++] = nums1[p1++];
//        }
//        while (p2<m){
//            ans[index++] = nums2[p2++];
//        }
//        for (int i = 0; i < ans.length; i++) {
//            nums1[i] = ans[i];
//        }
        // 逆向双指针
        int p1 = m-1;
        int p2 = n-1;
        int index = m+n-1; // 每次都选取最大的元素放在nums1后面 这样就不会有被覆盖的情况
        int cur;
        while(p1>=0||p2>=0){
            if(p1<0){
                cur = nums2[p2--];
            }else if(p2<0){
                cur = nums1[p1--];
            }else if(nums1[p1]>nums2[p2]){
                cur = nums1[p1--];
            }else {
                cur = nums2[p2--];
            }
            nums1[index--] = cur;
        }
    }
}
